package com.app.sort;

import java.util.Arrays;

public class InsertSort {

    public static void main(String[] args) {
        int[] data = new int[]{20, 1, 60, 7, 4, 3, 19};
        System.out.println("before:" + Arrays.toString(data));
        InsertSort is = new InsertSort();
        is.shell_sort(data);
        System.out.println("after:" + Arrays.toString(data));
    }


    public void sort(int[] data) {
        for (int i = 1; i < data.length; i++) {
            int first = data[i];
            int j = 0;
            for (j = i - 1; j >= 0 && data[j] > first; j--) {
                data[j + 1] = data[j];
            }
            data[j + 1] = first;

        }
    }

    public void binary_sort(int[] data) {
        for (int i = 1; i < data.length; i++) {
            int left = 0;
            int right = i - 1;
            int value = data[i];
            while (left <= right) {
                int middle = (left + right) / 2;
                if (value > data[middle]) {
                    left = middle + 1;
                } else {
                    right = middle - 1;
                }
            }
            for (int j = i - 1; j >= left; j--) {
                data[j + 1] = data[j];
            }
            data[left] = value;

        }
    }

    public void shell_sort(int[] data) {
        int gap = data.length / 2;
        while (gap > 0) {
            //从增量开始，对每个数字进行排序
            for (int index = gap; index < data.length; index++) {
                int k = index;
                int tmp = data[index];
                //从增量开始，对之前的数子进行比较，同样是假设前面的数字有序
                for (; k >= gap && data[k - gap] > tmp; k -= gap) {
                    data[k] = data[k - gap];
                }
                data[k] = tmp;
            }
            gap /= 2;
        }

    }
}
